package my.jwds.p33;

public class Search {

    public static void main(String[] args) {

        Solution obj = new Solution();
        long start = System.currentTimeMillis();
        System.out.println(obj.search(new int[]{4,5,6,7,0,1,2},
        4));
        System.out.println("运行时间:" + (System.currentTimeMillis() - start));
    }

    static class Solution {

        public int search(int[] nums, int target) {
            int rotate = searchRotatePoint(nums,0,nums.length-1);
            int res = binarySearch(nums,rotate, nums.length-1,target);

            if (res == -1){
                res = binarySearch(nums,0, rotate-1,target);
            }
            return res;
        }

        int searchRotatePoint(int[] nums,int lower,int upper){
            if (lower+1 == upper)return upper;
            int mid = (lower+upper) / 2;
            if (nums[mid] > nums[upper]){
                return searchRotatePoint(nums,mid,upper);
            }else if (nums[mid] < nums[lower]){
                return searchRotatePoint(nums,lower,mid);
            }
            return lower;
        }

        int binarySearch(int[] nums,int lower,int upper,int target){
            if (lower > upper)return -1;
            int mid = (lower+upper) / 2;
            if (nums[mid] > target){
                return binarySearch(nums, lower, mid-1, target);
            }else if (nums[mid] < target){
                return binarySearch(nums, mid+1, upper, target);
            }
            return mid;
        }
    }
}